"""
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)
"""
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        p,q,r = 0,0,1
        for i in range(2,n+1):
            p,q = q,r
            r = p+q
        return r
print(Solution().fib(2)) #1
print(Solution().fib(3)) #2
print(Solution().fib(4)) #3
